﻿//
// Created by Freeman on 2022/2/21.
//

#include <iostream>
#include <map>
#include <vector>
#include "../Headers/DP.h"
#include "../Headers/Exceptions.h"

using namespace std;

void NumberTower::solve() {
    // 读取输入
    int nLevels;
    cin >> nLevels;
    for (int i = 0; i < nLevels; i++) {
        tower.push_back(vector<int>());
        dist_dp.push_back(vector<int>());
        for (int j = 0; j <= i; j++) {
            int tmp;
            cin >> tmp;
            if (tmp <= 0) throw IllegalArgumentException("Node value must be positive.");
            tower.at(i).push_back(tmp);
            if (i < nLevels - 1) dist_dp.at(i).push_back(-1);
            else dist_dp.at(i).push_back(tmp); // 最后一层直接赋结点值
        }
    }

    cout << findLongestRoute(0, 0) << endl;
}

int NumberTower::findLongestRoute(int row, int col) {
    if (dist_dp[row][col] > 0) return dist_dp[row][col];
    else {
        dist_dp[row][col] = max(findLongestRoute(row + 1, col), findLongestRoute(row + 1, col + 1)) + tower[row][col];
        return dist_dp[row][col];
    }
}

void PAT_A1007::solve() {
    int nNum;
    cin >> nNum;
    vector<int> numbers;
    bool positive = false;
    for (int i = 1; i <= nNum; i++) {
        int tmp;
        cin >> tmp;
        if (tmp >= 0) positive = true;
        numbers.push_back(tmp);
    }
    if (!positive) {
        cout << 0 << " " << numbers[0] << " " << numbers[nNum - 1];
        return;
    }

    vector<int> dpLast(nNum); // dpLast[i]表示以i结尾的最大子序列之和
    vector<int> dpFirst(nNum); // dpFirst[i]表示以i起始的最大子序列之和
    dpLast[0] = numbers[0];
    dpFirst[nNum - 1] = numbers[nNum - 1];
    int maxSum = numbers[0];
    for (int i = 1; i < nNum; i++) {
        dpLast[i] = max(dpLast[i - 1] + numbers[i], numbers[i]);
        if (dpLast[i] > maxSum) maxSum = dpLast[i];
    }
    for (int i = nNum - 2; i >= 0; i--) {
        dpFirst[i] = max(dpFirst[i + 1] + numbers[i], numbers[i]);
    }
    int startIdx, endIdx;
    for (int i = 0; i < nNum; i++) {
        if (dpFirst[i] == maxSum) {
            startIdx = i;
            break;
        }
    }
    for (int i = 0; i < nNum; i++) {
        if (dpLast[i] == maxSum) {
            endIdx = i;
            break;
        }
    }
    cout << maxSum << " " << numbers[startIdx] << " " << numbers[endIdx];
}

void PAT_A1045_LIS::solve() {
    int nColors;
    cin >> nColors;
    int nFavoriteColors;
    cin >> nFavoriteColors;
    vector<int> order(201, -1); // 颜色-优先级映射
    for (int i = 1; i <= nFavoriteColors; i++) {
        int color;
        cin >> color;
        order[color] = i;
    }
    int stripeLen;
    cin >> stripeLen;
    vector<int> stripe;
    vector<int> dp(stripeLen, 1); // dp[i]表示以i结尾（必须包括i）的最长不下降子序列的长度
    for (int i = 1; i <= stripeLen; i++) {
        int color;
        cin >> color;
        if (order[color] == -1) continue; // 不是喜欢的颜色
        else stripe.push_back(color);
    }

    // 动态规划核心算法
    int maxLen = 1;
    for (int j = 1; j < stripe.size(); j++) {
        for (int i = 0; i < j; i++) {
            if (order.at(stripe[i]) > order.at(stripe[j])) continue;
            dp[j] = max(dp[j], dp[i] + 1); // 如果j移至i结尾的子序列后可以更长，那么移动j；这一过程可能发生多次
            if (dp[j] > maxLen) maxLen = dp[j];
        }
    }
    cout << maxLen << endl;
}

void PAT_A1045_LCS::solve() {
    // 读取最喜欢的颜色
    int nColors;
    cin >> nColors;
    int nFavoriteColors;
    cin >> nFavoriteColors;
    vector<bool> isFavorite(nColors + 1, false);
    // 色带及其对偶序列，用于求解LCS问题。对偶序列只存储几个最喜欢的颜色。为方便编程，有效元素下标从1开始。
    vector<int> stripe(1, 0), dualStripe(1, 0); // 预先插入0
    for (int i = 1; i <= nFavoriteColors; i++) {
        int color;
        cin >> color;
        isFavorite[color] = true;
        dualStripe.push_back(color);
    }
    // 读取色带
    int stripeLen;
    cin >> stripeLen;
    for (int i = 1; i <= stripeLen; i++) {
        int color;
        cin >> color;
        if (!isFavorite[color]) continue;
        else stripe.push_back(color);
    }

    // LCS（改）核心算法
    int rows = stripe.size(), cols = dualStripe.size();
    vector<vector<int>> dp;
    for (int i = 1; i <= rows; i++) dp.emplace_back(cols);
    // 边界初始化
    for (int i = 0; i < rows; i++) dp[i][0] = 0;
    for (int i = 0; i < cols; i++) dp[0][i] = 0;
    for (int i = 1; i < rows; i++) {
        for (int j = 1; j < cols; j++) {
            if (stripe[i] == dualStripe[j]) dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + 1;
            else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    cout << dp[rows - 1][cols - 1] << endl;
}

void PAT_A1040::solve() {
    string str;
    getline(cin, str);
    int strLen = str.length();
    if (strLen <= 1) {
        cout << strLen << endl;
        return;
    }

    int maxLen = 1; // 最长回文串长度
    vector<vector<bool>> dp(strLen, vector<bool>(strLen, false)); // dp[i][j]表示str[i~j]是否为回文串
    // 边界初始化
    for (int i = 0; i < strLen; i++) dp[i][i] = true;
    for (int i = 0; i < strLen - 1; i++) {
        dp[i][i + 1] = (str[i] == str[i + 1]);
        if (dp[i][i + 1]) maxLen = 2;
    }
    // 最长回文串DP核心算法
    for (int len = 3; len <= strLen; len++) {
        for (int i = 0; i + len - 1 < strLen; i++) {
            int j = i + len - 1;
            // 若str[i]!=str[j]，则为默认值false；由于外层循环按长度递增，dp[i + 1][j - 1]必然已计算
            if (str[i] == str[j]) dp[i][j] = dp[i + 1][j - 1];
            if (dp[i][j]) maxLen = len;
        }
    }

    cout << maxLen << endl;
}
